package com.hackerrank.contests.july13.challenges.computergame;

import java.util.Scanner;
import java.util.Stack;

public class Solution1 {
	private static int GCD(int a, int b) {
		return GCDmm(Math.min(a, b), Math.max(a, b));
	}
	private static int GCDmm(int m, int M) {
		if(m == 0)
			return M;
		return GCDmm(M % m, m);
	}
	public static void main(String[] args) {
		// scan input
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), A[] = new int[n], B[] = new int[n];
		for(int i = 0; i < n; i++)
			A[i] = in.nextInt();
		for(int i = 0; i < n; i++)
			B[i] = in.nextInt();
		
		// calculate matchings
		boolean m[][] = new boolean[n][n];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				m[i][j] = GCD(A[i], B[j]) > 1;
		
		// no matchings
		int ma[] = new int[n], mb[] = new int[n];
		for(int i = 0; i < n; i++) {
			ma[i] = -1;
			mb[i] = -1;
		}
		
		while(true) {
			int i = -1, j = -1;
			Stack<Integer> pb = null;
			boolean pf = false;
			while(!pf) {
				// find next non matched vertices
				if(i < 0) {
					// find first i and first j
					for(i = 0; i < n && ma[i] >= 0; i++);
					for(j = 0; j < n && mb[j] >= 0; j++);
				} else {
					// find next j
					for(j++; j < n && mb[j] >= 0; j++);
					// if cannot find next j find next i and first j
					if(j >= n) {
						for(i++; i < n && ma[i] >= 0; i++);
						for(j = 0; j < n && mb[j] >= 0; j++);
					}
				}
				
				if(i >= n || j >= n) {
					int max = 0;
					for(int k = 0; k < n; k++)
						if(ma[k] >= 0)
							max++;
					System.out.println(max);
					return;
				}
				
				// find path between i and j
				pb = new Stack<Integer>();
				out: while(true) {
					int t = pb.isEmpty() ? -1 : pb.peek();
					if(t == j) {
						// path found
						pf = true;
						break;
					}
					int s = t < 0 ? i : mb[t];
					int k = 0;
					for(; k < n; k++)
						if(m[s][k] && (k == j || mb[k] >= 0) && !pb.contains(k)) {
							pb.push(k);
							break;
						}
					in: while(k >= n) {
						if(pb.isEmpty()) {
							pf = false;
							break out; // no path found
						}
						pb.pop();
						int pt = pb.isEmpty() ? -1 : pb.peek(), ps = pt < 0 ? i : mb[pt];
						for(k = t + 1; k < n; k++)
							if(m[ps][k] && (k == j || mb[k] >= 0) && !pb.contains(k)) {
								pb.push(k);
								break in;
							}
						t = pt;
						s = ps;
					}
				}
			}
			int t = pb.pop();
			while(!pb.isEmpty()) {
				int pt = pb.pop();
				int ps = mb[pt];
				ma[ps] = t;
				mb[t] = ps;
				t = pt;
			}
			ma[i] = t;
			mb[t] = i;
		}
	}
}
